9
Encontrando Concurrencia del Diseño del Espacio
Descomposición de tareas
Análisis de descomposición
Descomposición de dominios
Ordenar grupos
Compartir datos
Análisis de dependencias
Agrupar tareas
10
Encontrando concurrencia
Del código serial:
Usa un analizador, tal como “Intel® VTuneTM Performance Analyzer”
Identifica hotspots en una aplicación
Examina el código en los hotspots
Determina cuando las tareas dentro de los hotspots pueden ejecutarse independientemente
De un documento de diseño:
Examina los componentes de diseño
Encuentra componentes que contienen operaciones independientes
11
Espacio de Diseño de la Estructura del Algoritmo
Estructura usada para organizar computo para soportar paralelismo
(Gp:) Pipeline
(Gp:) Organizado por flujo de datos
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por tareas
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por datos
(Gp:) Datos Recursivos
(Gp:) ¿Regular?
(Gp:) ¿Irregular?
(Gp:) Paralelismo de tareas
(Gp:) Descomposición Geométrica
(Gp:) Divide y Vencerás
(Gp:) Coordinación basada en eventos
¿Cómo está estructurado el cómputo?
12
Consideraciones que afectan a las estructuras de los algoritmos
Las siguientes consideraciones afectan las metas de diseño,
Eficiencia
El programa paralelo debe ejecutarse rápidamente y hacer buen uso de los recursos de procesamiento
Simplicidad
Algoritmos simples (fáciles de entender) son más fáciles de desarrollar, depurar, verificar y mantener
Portabilidad
Los programas deben ejecutarse en el rango más amplio de computadoras paralelas
Escalabilidad
Los algoritmos paralelos deben ser efectivos en un amplio rango de número de hilos y núcleos, y tamáños de datos o conjuntos de datos
13
Consideraciones que afectan a las estructuras de los algoritmos
Puede haber conflictos entre dos o más de las consideraciones (Eficiencia, Simplicidad, Portabilidad, Escalabilidad)
El balanceo de las consideraciones es crítico para obtener el mejor código paralelo
14
Estructuras de Soporte del Espacio de Diseño
Bloques de construcción de alto nivel usados para organizar el código fuente
Categorizados en estructuras de programa y estructuras de datos
Cola compartida
Paralelismo de Ciclos
Maestro/Esclavo
Estructuras de Programa
Estructuras de Datos
Datos compartidos
SPMDSingle Program Multiple Data
Arreglo distribuido
Fork/Join
15
Mecanismos de Implementación del Espacio de Diseño
Bloques de construcción de bajo nivel implementando bloques de construcción específicos usados en cómputo paralelo
No propiamente patrones de diseño; incluidos para hacer el patrón del lenguaje autónomo
* UE = Unidad de Ejecución
Control de Procesos
Gestión del UE*
Control de hilos
Com. Colectiva
Comunicaciones
Paso de Mensajes
Otras Com
Exclusión Mutua
Sincronización
Sinc. de Memoria/Vallas
Barreras
16
Agenda
Patrón de estructura de lenguaje
El patrón de paralelismo de tareas
El patrón de descomposición geométrica
Estructuras de Soporte
Resumen
17
Estructuras de Algoritmos del Espacio de Diseño
(Gp:) Pipeline
(Gp:) Organizado por flujo de datos
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por tareas
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por datos
(Gp:) Datos Recursivos
(Gp:) ¿Regular?
(Gp:) ¿Irregular?
(Gp:) Paralelismo de tareas
(Gp:) Descomposición Geométrica
(Gp:) Divide y Vencerás
(Gp:) Coordinación basada en eventos
¿Cómo está estructurado el cómputo?
18
Patrón de Paralelismo de Tareas
Problema:
¿Cómo puedes explotar la concurrencia en términos de un conjunto de distintas tareas?
Ejemplos:
Ray tracing – el cómputo de cada rayo es independiente al cómputo de cualquier otro rayo
Dinámica Molecular – Actualización de las fuerzas sobre los átomos es independiente; combinando todos las fuerzas de los cómputos parciales de cada hilo se hace cuando terminan todas las fuerzas son calculadas
19
Contexto del Patrón de Paralelismo de Tareas
Cada algoritmo es una colección de tareas concurrentes
Puede encontrarse a través de la inspección del código
El factor común es descomponer la computación en una colección de tareas concurrentes
Las tareas pueden ser completamente independientes
Las tareas pueden tener dependencias que necesitan satisfacerse
20
Contexto del Patrón de Paralelismo de Tareas
Las tareas son usualmente conocidas a principio de la computación
Las tareas pueden surgir dinámicamente (por ejemplo, búsqueda en un árbol)
Normalmente deben esperar a que todas las tareas terminen antes de completar el problema
Puede ser capaz de terminar cuando se encuentra la solución antes de completar todas las tareas
Ejemplo: Búsqueda – si el elemento se encuentra, no es necesario seguir buscando, si el elemento no estaba presente, debe terminar de la búsqueda para asegurarse
21
Consideraciones del Patrón de Paralelismo de Tareas
Tamaño de Tareas
Tareas pequeñas para balancear carga vs. Tareas grandes para reducir sobrecarga de planificación
Administrando Dependencias
Sin destruir eficiencia, simplicidad, o escalabilidad
22
Soluciones del Patrón de Paralelismo de Tareas
Tres elementos de diseño clave para patrones de paralelismo de tareas
Tareas y cómo se definen
Las dependencias entre las tareas
Planificación de las tareas a hilos
23
Definiendo Tareas
Descomponer un algoritmo serial con descomposición de tareas de reunir dos criterios:
Debe ser al menos un número de tareas como hilos (o núcleos)
Preferible que haya más tareas que hilos
Mayor flexibilidad en la planificación
Ayudar a lograr una carga más equilibrada entre los hilos
La cantidad de cómputo dentro de una tarea debe ser lo suficientemente grande como para compensar la sobrecarga de gestión de tareas e hilos
Si la descomposición inicial no reúne estos criterios, deben considerarse descomposiciones alternas
24
ACTIVIDAD: ejemplo de definición de tareas
Considere una aplicación de procesamiento de imágenes, donde cada pixel es independiente
¿Cuál es el nivel apropiado de descomposición de tareas?
Tarea == un pixel
Tarea == una línea
Tarea == bloques dentro de la imagen
25
Administrando Dependencias en Soluciones en el Patrón de Paralelismo de Tareas
Ordenar los acuerdos entre las tareas pueden ser manejados para forzar grupos de tareas a ejecutarse en orden
(Gp:) Paisaje
(Gp:) Construir Paredes
(Gp:) Poner techo
(Gp:) Tejas en el techo
(Gp:) Instalación
Eléctrica
(Gp:) Enjarre
(Gp:) Parte Exterior
26
Gestionando Dependencias en Patrones de Solución de Paralelismo de Tareas
Resolver dependencias de datos puede ser más complicado
El caso más simple es tener no dependencias (vergonzosamente paralelas)
Estrategias para manejar dependencias de datos entre tareas:
Removerlas (replicando datos)
Transformando variables de inducción
Reducciones
Protegiendo explícitamente (patrón de datos compartidos)
27
Calcula global X
Calcula global Y
Calcula global Z
Envía señal X,Y,Z listos
For i = 1, 10
Calcula a[i] = F(X,Y,Z,b[i])
Dependencias Removibles
No una dependencia verdadera, pero una dependencia aparente que puede eliminarse con transformación de código
La solución más simple sería crear, inicializar, y usar variables locales
Puede implicar la replicación de trabajo dentro de los hilos
(Gp:) Algoritmo Serial:
(Gp:) Calcula X
Calcula Y
Calcula Z
For i = 1, 20
Calcula a[i] = F(X,Y,Z,b[i])
Espera que X,Y,Z estén listos
For i = 11, 20
Calcula a[i] = F(X,Y,Z,b[i])
Hilo 1
Hilo 2
Calcula local X
Calcula local Y
Calcula local Z
For i = 11, 20
Calcula a[i] = F(X,Y,Z,b[i])
Calcula local X
Calcula local Y
Calcula local Z
For i = 1, 10
Calcula a[i] = F(X,Y,Z,b[i])
28
Dependencias Removibles
Las variables de inducción se incrementan en cada pasada dentro del ciclo
Arreglar reemplazando los incrementos con expresiones equivalentes en función al índice del ciclo
i1 = 4;i2 = 0;for (I = 0; I < N; I++)
{ B[i1++] = … ;
i2 = i2 + I; A[i2] = … ;}
for (I = 0; I < N; I++)
{
B[I+4] = …;
A[((I+1)*I)/2)] = …;}
29
Dependencias “Separables”
Dependencias en estructuras de datos compartidas usadas para acumular de datos calculados en cada hilo
Mueve la acumulación fuera de la concurrencia:
Replica los datos a cada hilo, inicialízalos como se requiera
Ejecuta las tareas usando la copia local de la estructura de datos
Al completarse, combina todas las copias en una estructura de datos global
30
Dependencias “Separables”
El ejemplo más común: Reducción
Una colección de datos se reduce a un solo valor aplicando una operación binaria a todos los elementos de la colección
La operación binaria debe ser asociativa y conmutativa
for (int i = 0; i < N; i++)
sum += a[i] * b[i];
31
Protección Explícita de Datos Compartidos
Si la dependencia no puede removerse o separarse desde las tareas, entonces los datos compartidos que se actualizan deben protegerse
Implementa una región crítica en el código que accesa datos compartidos
Si se hace cualquier actualización, todos los accesos (lectura y escritura) deben estar en una región crítica
Agrega lógica de programación para forzar la exclusión mutua en una región crítica
Usa objetos de sincronización apropiada para crear exclusión mutua
32
Planificando Tareas
Las tareas deben asignarse a hilos para que se ejecutenPlanifica tareas con carga de trabajo balanceadaUsuales dos tipos de planificación
Planificación estática
Las tareas se asignan a hilos al inicio del cómputo y no cambian
Fácil de programar y provoca poca sobrecarga
Debe usarse siempre que sea posible
Planificación dinámica
Las tareas se asignan conforme procede el cómputo
33
Consideraciones de Planificación Estática
El trabajo debe diferenciarse con id de hilo único para cada hilo
Si las tareas son colecciones de llamadas a funciones independientes separadas
Agrupa las llamadas en tareas que son asignadas a hilos
Si las tareas son iteraciones de ciclos, dos planificaciones posibles
Divide el número total de iteraciones entre el número de hilos y asigna un bloque de iteraciones a los hilos
Inicia cada conjunto de hilos de iteración por número de id de hilo (0..N-1), cada hilo calcula cada enésima iteración
34
Consideraciones de Planificación Dinámica
Usada cuando el tamaño de la ejecución de tareas es variable e impredecible
Métodos posibles para planificación dinámica de tareas
Usar una estructura compartida para mantener las tareas
Si las tareas se pueden encapsular dentro de una estructura, crea una cola global que tener y despachar tareas cuando los hilos necesiten más trabajo
Si las tareas se almacenan en un archivo, los hilos comparten acceso para leer tareas del archivo
35
Consideraciones de Planificación Dinámica
Métodos posibles para planificación dinámica de tareas
Algunas tareas pueden tomar pre-procesamiento en orden de estar listas para que se les asigne computación
Usa un hilo extra para obtener tareas listas para los hilos y asignarlas a hilos cuando sean solicitadas (Patrón maestro/esclavo)
Usar un hilo extra para poner tareas en una cola compartida para que otros hilos las tomen conforme las necesiten (patrón Productor/Consumidor)
Si las tareas están indexadas, crea un contador compartido para mantener registro de y asignar la próxima tarea a ejecución
36
Z
X
Y
CASO DE ESTUDIO: Evitar Desastres Aereos
37
CASO DE ESTUDIO: Evitar Desastres Aereos
Escenario de un conjunto de aviones alrededor de un aeropuerto
¿Hay dos aviones demasiado cerca entre ellos mismos?
Si, envía un mensaje de advertencia y registra el evento
Lleva registro del número de advertencias generadas por un avión en el escenario
Será usado para determinar cual vuelo puede estar más en peligro
38
CASO DE ESTUDIO: Evitar Desastres Aereos
Los aviones tienen un número de vuelo y una posición actual en un espacio 3-D
X y Y son la posición con respecto a la tierra (mapa)
Z es la altitud actual
Pseudo-código en la siguiente diapositiva
El cálculo de la distancia se usa para determinar peligro potencial
39
CASO DE ESTUDIO: Posicionamiento de Aviones
function AirplanePositions (N, M, Flights)
int const N, M; //Número de aviones, aeropuertos
Array of Airplane_t :: Flights(N); // arreglo de estructuras de aviones
Real :: distX, distY, distZ, distance
loop [j = 0, N]
loop [k = j+1, N]
distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2
distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2
distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2
distance = sqrt(distX + distY + distZ)
if (distance < SAFETY_MARGIN)
PrintWarning(Flights[j],Flights[k])
Flights[j].numWarnings++
Flights[k].numWarnings++
end loop[k]
end loop[j]
end function AirplanePositions
40
function AirplanePositions (N, M, Flights)
int const N, M; //number of planes, airports
Array of Airplane_t :: Flights(N); // array of planes structs
Real :: distX, distY, distZ, distance
loop [j = 0, N]
loop [k = j+1, N]
distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2
distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2
distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2
distance = sqrt(distX + distY + distZ)
if (distance < SAFETY_MARGIN)
PrintWarning(Flights[j],Flights[k])
Flights[j].numWarnings++
Flights[k].numWarnings++
end loop[k]
end loop[j]
end function AirplanePositions
El cálculo de la distancia entre cada avión es una tarea
CASO DE ESTUDIO: Posicionamiento de Aviones– Definir tareas
41
function AirplanePositions (N, M, Flights)
int const N, M; //Número de aviones, aeropuertos
Array of Airplane_t :: Flights(N); // arreglo de estructuras de aviones
Real :: distX, distY, distZ, distance
loop [j = 0, N]
loop [k = j+1, N]
distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2
distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2
distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2
distance = sqrt(distX + distY + distZ)
if (distance < SAFETY_MARGIN)
PrintWarning(Flights[j],Flights[k])
Flights[j].numWarnings++
Flights[k].numWarnings++
end loop[k]
end loop[j]
end function AirplanePositions
Dar a cada hilo una copia local de esas variables de trabajo
La Actualización de variables compartidas debe protegerse
Cada hilo necesitará una copia local de los índices del ciclo j,k
CASO DE ESTUDIO: Posicionamiento de Aviones – Dependencias
42
CASO DE ESTUDIO: Posicionamiento de Aviones ¿Cómo deben planificarse las tareas?
Planificación Estática
Divide hasta N aviones y asígnalos a hilos
Asignar N/(# de hilos) aviones a un hilo
Asignar cada n-ésimo avión a cada hilo, iniciar con id del hilo
Planificación Dinámica
Establecer contador global (0..N-1)
Los hilos acceden el contador para el siguiente[j], incrementa el contador
Deben proteger el acceso e incrementar el contador global
loop [j = 0, N]
loop [k = j+1, N]
if (NOT j.Landed OR NOT k.Landed) then
distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2
distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2
distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2
distance = sqrt(distX + distY + distZ)
if (distance < SAFETY_MARGIN)
LogWarning(Flights[j],Flights[k])
Flights[j].numWarnings++
Flights[k].numWarnings++
end loop[k]
end loop[j]
43
ACTIVIDAD: Dinámica Molecular
¿Qué son las tareas dentro del pseudocódigo?
¿Hay dependencias? ¿Cómo pueden resolverse?
¿Cómo deben planificarse las tareas para ejecutarse en hilos?
44
ACTIVIDAD: Código de la Dinámica Molecular
Colecciones de átomos calculan fuerzas entre pares de átomos
Solo pares de átomos que están con un radio igual a un límite preestablecido
La lista de vecinos para cada átomo determina que otros átomos están dentro del radio
Tercera ley de Newton: La fuerza del Atom[i] en el Atom[j] es el negativo del Atom[j] en el Atom[i]
Si el Atom[j] está en la lista de vecinos del Atom[i], entonces el Atom[i] no estará en la lista para el Atom[j]
Pseudo-código en la siguiente diapositiva
No se requieren cálculos físicos para este ejercicio
No se muestran como los vecinos hacen sus actualizaciones
45
ACTIVIDAD: Código de la Dinámica Molecular
function non_bonded_forces_all (N, Atoms, neighbors, Forces)
Int const N //number of atoms
Array of Real :: atoms(3,N) // 3D coordinates
Array of Real :: Forces(3,N) // force in each dimension
Array of List :: neighbors(N) // atoms in cutoff volume
Real :: forceX, forceY, forceZ
loop [i] over atoms
loop [j] over neighbors(i)
forceX = non_bonded_force_pair(atoms(1,i), atoms(1,j))
forceY = non_bonded_force_pair(atoms(2,i), atoms(2,j))
forceZ = non_bonded_force_pair(atoms(3,i), atoms(3,j))
Forces(1,i) += forceX; Forces(1,j) -= forceX;
Forces(2,i) += forceY; Forces(2,j) -= forceY;
Forces(3,i) += forceZ; Forces(3,j) -= forceZ;
end loop[j]
end loop[i]
end function non_bonded_forces_all
46
Agenda
Patrón de estructura de lenguaje
El patrón de paralelismo de tareas
El patrón de descomposición geométrica
Estructuras de Soporte
Resumen
47
Estructuras de Algoritmos del Espacio de Diseño
(Gp:) Pipeline
(Gp:) Organizado por flujo de datos
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por tareas
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por datos
(Gp:) Datos Recursivos
(Gp:) ¿Regular?
(Gp:) ¿Irregular?
(Gp:) Paralelismo de tareas
(Gp:) Descomposición Geométrica
(Gp:) Divide y Vencerás
(Gp:) Coordinación basada en eventos
¿Cómo está estructurado el cómputo?
48
Patrón de Descomposición Geométrica
Problema:
¿Como un algoritmo paralelo puede estar organizado alrededor de una estructura de datos que puede descomponerse en “fragmentos” independientes y concurrentemente actualizables?
49
Patrón de Descomposición Geométrica
Ejemplos:
Predicción del clima – Divide el área de interés en secciones discretas, no sobrepuestas; calcula los efectos del viento, tierra, sol, humedad, clima en secciones vecinas, etc. Iterativamente
Fractales de Newton-Raphson – Para cada punto dentro de un plano complejo, calcula el número de iteraciones requeridas para alcanzar la raíz del polinomial; punto de color apropiadamente
50
Contexto del Patrón de Descomposición Geométrica
Muchos problemas pueden entenderse mejor como una secuencia de operaciones en el núcleo de una estructura de datos
Todos los elementos de la estructura se actualizan o se usan para cómputo
51
Contexto del Patrón de Descomposición Geométrica
La estructura se divide en sub-estructuras contiguas o sub-regiones
Arreglos: divide entre una o más dimensiones
Listas: define sublistas de elementos discretos
Grafos y Árboles: construye sub-grafos o sub-árboles
52
Contexto del Patrón de Descomposición Geométrica
Usaremos el término genérico fragmento para referir una sub-región
La descomposición de datos en fragmentos implica una división del cómputo en tareas para operar en elementos de cada fragmento
Las tareas se ejecutarán concurrentemente
Cada tarea actualizará el fragmento asociado
Las tareas pueden requerir datos de fragmentos vecinos que deben ser compartidos
Los fragmentos vecinos contienen datos que estaban “cerca” en la estructura de datos original
53
Propuestas del Patrón de Descomposición Geométrica
Metas: simplicidad, portabilidad, escalabilidad, y eficiencia
Fragmentos de datos deben asignarse a hilos
El balanceo de carga puede ser un factor, especialmente cuando se usan fragmentos de tamaño variable
El cómputo asociado debe ser ejecutado por el hilo
Asegurarse que los datos necesarios para actualizar los fragmentos están disponibles cuando se requieren
Los datos desde dentro de un fragmento son de fácil acceso
Acceder datos esenciales de fragmentos vecinos pueden requerir coordinación entre hilos
54
Patrones de Soluciones de Descomposición Geométrica
Deben considerarse las siguientes actividades clave:
Descomposición de datos
Particionar la estructura de datos global en fragmentos
Considera granularidad y la forma de los fragmentos
Operación de intercambio
Asegurarse que cada tarea tenga acceso a todos los datos necesarios para la actualización
¿Se requiere tener disponibles datos “externos”?
Operación de actualización (cómputo)
Actualizando los elementos dentro del fragmento
Normalmente la mayor parte del cómputo
Distribución de datos y planificación de tareas
Como mapear fragmentos y asociar cómputo a hilos
55
1. Descomposición de Datos – Granularidad
La granularidad de la descomposición de los datos tendrá un impacto significativo en el rendimiento y eficiencia de la aplicación
Descomposición Grano-grueso
Menos fragmentos pero más grandes
Requiere menor cantidad de datos compartidos (sincronización/comunicación)
Descomposición Grano-fino
Más fragmentos pero más pequeños
Puede haber (mucho) más fragmentos que hilos; más fácil para el balanceo de carga
Mayor cantidad de datos compartidos y sincronización
56
1. Descomposición de Datos – Granularidad
La granularidad óptima puede ser difícil de obtener matemáticamente al principio de la computación
Experimentos para encontrar el mejor tamaño en la descomposición
Si las cargas de trabajos varían entre ejecuciones, el tamaño de la descomposición puede ser parametrizable dentro de la aplicación
Bueno para escalabilidad de la aplicación
57
1. Descomposición de Datos – Forma (Arreglo)
La forma de los fragmentos puede afectar la cantidad de comunicación y sincronización requerida
Los datos a compartir usualmente son valores de frontera de los fragmentos
Datos compartidos escalan de la superficie de los fragmentos
La computación escala con el volumen de los fragmentos (número de elementos de datos en un fragmento)
(Gp:) 16 celdas, 4 compartidas
(Gp:) 16 celdas, 8 compartidas
58
1. Descomposición de Datos – Forma (Arreglo)
Tamaño y forma de los fragmentos pueden ser afectados por otros factores
Tamaño línea caché, renglón-mayor o columna-mayor, código fuente antes/después
(Gp:) 16 celdas, 4 compartidas
(Gp:) 16 celdas, 8 compartidas
59
1. Descomposición de Datos – Forma (Gráfico)
La superficie del subgrafo puede dividirse a lo ancho para dividirse en subgrafos
Asume que los datos deben compartirse a través de las aristas
La mejor división de nodos a hilos para minimizar vecinos asignados a hilos diferentes
60
ACTIVIDAD: Misión de descomposición
Describe esquemas de descomposición para los siguientes conjuntos de datos:
Red de cuadros representando la masa de tierra y costa de Australia
Catálogo de libros en una librería
Gráfica que representa un mapa de 3000 ciudades en México (nodos) y carreteras entre ellos (aristas)
61
2. Operación de Intercambio
Factor clave en un patrón correcto de Descomposición Geométrica
Asegurar que el intercambio de datos entre segmentos vecinos sea eficiente
¿Copiar datos a estructuras de datos locales o accederlos conforme se necesiten?
62
2. Operación de Intercambio
Copiar datos a una estructura de datos local
Si hay datos disponibles antes de una operación de actualización y no cambiará durante la copia
Requiere memoria extra por hilo, pero no bloqueos en las copias
Acceder los datos conforme se requieren
Obtiene ventaja de la memoria compartida entre hilos
Retrasos en la coordinación entre hilos mientras los datos son necesitados
(Gp:) Debe haber coordinación entre hilos para asegurarse que los datos están disponibles y no cambiarán durante el intercambio
63
3. Operación de Actualización
Ejecución de las tareas asociadas actualizará concurrentemente la estructura de datos
64
3. Operación de Actualización
Consideraciones de la codificación para la interacción de intercambio y actualización
Si todos los datos están disponibles al inicio de las tareas y no cambiarán durante el cómputo, la paralelización será más fácil y probablemente eficiente
Si se van a copiar datos no locales de otros fragmentos antes de operaciones de cómputo de actualización, añade una fase de recopilación de datos antes de comenzar la actualización
Si no se van a acceder datos no locales a través de operaciones de actualización, agrega código para asegurarse que se encuentran los datos correctos y garantizar que se observa un protocolo de acceso adecuado (exclusión mutua)
Mezclar operaciones de intercambio y actualización pueden complicar la lógica de la aplicación, especialmente para asegurar que se obtienen datos correctos
65
4. Distribución de Datos y Planificación de Tareas
Determina que hilos actualizarán que segmentos de datos
La distribución estática es lo más simple
La coordinación para el intercambio será sencilla para determinar e implementar
Lo más apropiado cuando la cantidad de cómputo en las tareas es uniforme
La distribución dinámica es útil para el balanceo de carga
Requiere (muchas) más tareas que hilos
La operación de intercambio será más compleja
Debe asegurarse que las actualizaciones de datos no-locales se ha completado
66
4. Distribución de Datos y Planificación de Tareas
¿Qué hay acerca de redistribución dinámica de la distribución estática inicial?
Si la cantidad de trabajo por hilo cambia sobre el curso del cómputo
Ejemplo: operación de matriz que elimina renglones/columnas
Aplicación que puede reconfigurar la distribución de tareas/datos para la carga de trabajo
La Ganancia en el rendimiento debe superar la sobrecarga añadida por la re-distribución
67
CASO DE ESTUDIO: Multiplicación de Matrices
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
C[i][j] = 0.0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
for (k = 0; k < L; k++)
C[i][j] += A[i][k] * B[k][j];
B
A
C
¿Qué se puede calcular de manera independiente?
Elementos individuales de C
Renglones de C (usando todo de B)
Columnas de C (usando todo de A)
Bloques de C
68
CASO DE ESTUDIO: Multiplicación de Matrices
¿Qué estructura de datos grande necesita ser actualizada?
¿Cómo debe descomponerse la estructura de datos? ¿Qué granularidad será la mejor?
¿Qué datos necesitan compartirse entre tareas asociadas con los fragmentos de datos? ¿Hay datos no locales que requieren intercambiarse?
¿Cómo debemos asignar los fragmentos a los hilos? ¿Estático o Dinámico?
69
CASO DE ESTUDIO: Multiplicación de Matrices con Posibles Respuestas
¿Qué estructura de datos grande necesita ser actualizada?
La matriz C
¿Cómo debe descomponerse la estructura de datos? ¿Qué granularidad será la mejor?
Elementos individuales parece que sería grano demasiado fino
Grupos de renglones entran en renglones más accesados y es grano grueso
Los bloques pueden usarse enfocándose en el tamaño y utilización del caché
70
CASO DE ESTUDIO: Multiplicación de Matrices con Posibles Respuestas
¿Qué datos necesitan compartirse entre tareas asociadas con los segmentos de datos? ¿Hay datos no locales que requieren intercambiarse?
Elementos de los arreglos A y B son compartidos (pero no actualizados)
Si estos caben en la memoria, pueden compartirse sin intercambiarse
¿Cómo debemos asignar los segmentos a los hilos? ¿Estático o Dinámico?
Como no se requiere intercambio de datos, la distribución estática es la más simple
71
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
C[i][j] = 0.0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
for (k = 0; k < L; k++)
C[i][j] += A[i][k] * B[k][j];
(Gp:) Modifica los límite del ciclo “i”, basado en un identificador de hilo único, asignando grupos de renglones a hilos individuales
(Gp:) Cada hilo requerirá copias locales de todas las variables índices de los ciclos
CASO DE ESTUDIO: Multiplicación de Matrices
72
ACTIVIDAD: Juego de la vida
¿Cuál es la mayor cantidad de datos que pueden actualizarse concurrentemente?
¿Cómo deben descomponerse estos datos?
¿Cómo deben planificarse los datos y tareas para ejecutarse en hilos?
¿Qué consideraciones se necesitan tomar en cuenta para la carga de trabajo?
73
Agenda
Patrón de estructura de lenguaje
El patrón de paralelismo de tareas
El patrón de descomposición geométrica
Estructuras de Soporte
SPMD
Paralelismo de Ciclos
Maestro/Esclavo
Resumen
74
Estructuras de Soporte, Espacio de Diseño
Bloques de construcción de alto nivel usados para organizar el código fuente
Categorizados en estructuras de programa y estructura de datos
Cola compartida
Paralelismo de ciclos
Maestro esclavo
Estructuras del Programa
Estructuras de Datos
Datos compartidos
SPMD
Arreglo distribuido
Fork/join
Fork/join
75
Patrón SPMD
Problema
¿Cómo estructuramos un programa paralelo para hacer iteraciones entre hilos que sean fácilmente manejables para integrarlos con los núcleos de computación?
Contexto
Las iteraciones entre hilos deben estar bien orquestadas para lograr soluciones correctas y eficientes
Muchos algoritmos paralelos tienen operaciones similares llevadas a cabo por cada hilo, pero puede haber algunos cuantos requerimientos ligeramente diferentes para un conjunto de hilos o datos
Solo los algoritmos más complejos necesitan instrucciones y flujos de datos muy diferentes en cada hilo
76
Patrón SPMD
Propuesta
Sería más fácil balancear las necesidades conflictivas de escalabilidad y de mantenimiento dentro de una solo código fuente en vez de que sea a través de varios archivos fuentes
77
Patrón SPMD – Solución
Una sola aplicación creará hilos para ejecutar código y funciones dentro del código fuente
Dada la naturaleza de la programación multihilos, el patrón SPMD es el default
78
Patrón SPMD – Solución
Codificando Elementos para implementar el patrón SPMD
Obtener un identificador único
Asignar un ID para cada hilos, usualmente de 0..N-1
Usa el ID para diferenciar comportamiento entre hilos diferentes
Las instrucciones de saltos pueden usarse para asignar bloques de código
Usar el ID en los cálculos del índice del ciclo para dividir iteraciones entre los hilos
79
Patrón SPMD – Solución
Distribuye datos
Decompone datos globales en fragmentos y accede los fragmentos basándote en el ID
Finaliza
Si datos globalmente relevantes fueron distribuidos entre hilos, se requieren recombinar los resultados parciales
80
Patrón SPMD – Discusión
Los programas SPMD están mas cercanamente alineados con ambientes distribuidos de paso de mensajes
Un solo programa que crea hilos es el default para la programación multihilos
Los hilos dentro del mismo proceso comparten código y datos
Más relevante con modelos de hilos generales que OpenMP
81
Patrón de Paralelismo de Ciclos
Problema
¿Como estructurar un programa paralelo de un programa serial donde un conjunto de ciclos computacionalmente intensivos dominan el tiempo de ejecución?
82
Patrón de Paralelismo de Ciclos
Contexto
Un gran número de aplicaciones científicas y técnicas hacen uso de construcciones iterativas (basadas en ciclos)
La meta es “hacer evolucionar” código secuencial en código paralelo transformando ciclos para ejecutar iteraciones separadas en hilos
Las iteraciones de ciclos deben funcionar bien como tareas paralelas
Computacionalmente intensivas
Expresar suficiente concurrencia
La mayoría independientes
Quitar las dependencias entre ciclos si están presentes
Este patrón es particularmente relevante para usar OpenMP, Intel TBB
83
Patrón de Paralelismo de Ciclos
Equivalencia Secuencial
Programa que arroja resultados idénticos con uno o muchos hilos
Errores de variaciones de redondeo pueden ser aceptables
Código secuencialmente equivalente es más fácil de escribir y mantener
Paralelismo Incremental
Es más fácil mantener la correctud si las transformaciones del ciclo pueden hacerse y probarse una a la vez
Puede ser difícil con modelos generales de hilos y distribución de datos a segmentos locales (se necesita transformación de “todo el código”)
84
Patrón de Paralelismo de Ciclos
Utilización de Memoria
Patrones de acceso de datos deben caber bien con las jerarquías de memoria
Dividir las iteraciones para los hilos puede arruinar los patrones de acceso secuencial
Puede ser necesario re-estructurar los para un mejor acceso
85
Patrón de Paralelismo de Ciclos – Solución
Un estilo de programación alineado con OpenMP, Intel TBB
Modelos generales de paralelismo pueden usarse con asignaciones de iteraciones de ciclos provistas por el programador
86
Patrón de Paralelismo de Ciclos – Solución
Codificando elementos para implementar el patrón de paralelismo de ciclos
Emcontrar hotspots
Identifica los ciclos computacionalmente más intensivos inspeccionando el código, entendiendo el algoritmo, o usa un programa para el análisis
Eliminar dependencias de los ciclos
Encuentra dependencias entre iteraciones o conflictos de datos
Remueve dependencias o protege daos con sincronización
Paraleliza los ciclos
Divide las iteraciones entre hilos
Optimiza la planificación de ciclos
Planifica iteraciones de ciclos para asegurar el balanceo de carga
87
Patrón de Paralelismo de Ciclos – Consideraciones
El tiempo de cómputo dentro de las iteraciones debe ser suficiente para superar la sobrecarga de crear hilos y asignarles trabajo
Solución: Mezclar hilos
Dada una secuencia de ciclos con rangos de índices consistentes, mezclar esos ciclos en un solo ciclo incrementará el trabajo por iteración del ciclo resultante
88
Patrón de Paralelismo de Ciclos – Consideraciones
El número más grande de iteraciones disponibles, habrá mayor flexibilidad para decisiones de planificación
Solución: Unir ciclos anidados
Combinar ciclos anidados puede llevarnos a un solo ciclo con un contador grande de iteraciones
Contadores de iteraciones grandes pueden también permitir mejores oportunidades de superar la sobrecarga
89
Ejemplo de unir hilos
#define N 23
#define M 1000
. . .
for (k = 0; k < N; k++)
for (j = 0; j < M; j++)
w_new[k][j] = DoSomeWork(w[k][j], k, j);
#define N 23
#define M 1000
. . .
for (kj = 0; kj < N*M; kj++) {
k = kj / M;
j = kj % M;
w_new[k][j] = DoSomeWork(w[k][j], k, j);
}
(Gp:) Un número primo de iteraciones nunca permitirá un balanceo de carga perfecto
(Gp:) ¿Paraleliza el ciclo interno? ¿Hay suficientes iteraciones para superar la sobrecarga de la gestión de los hilos?
(Gp:) DIV y MOD con el valor límite del ciclo interno
Estos cálculos son sobrecarga
(Gp:) Un número grande de iteraciones da más oportunidad de balancear la carga y eliminar la sobrecarga
90
Dividendo Iteraciones de un Ciclo – OpenMP
Añade pragma de OpenMP para dividir las iteraciones entre hilos
Añade cláusulas de ambiente de datos y planificación como sea necesario
#define N 23
#define M 1000
. . .
#pragma omp for private(k,j) schedule(static, 500)
for (kj = 0; kj < N*M; kj++) {
k = kj / M;
j = kj % M;
w_new[k][j] = DoSomeWork(w[k][j], k, j);
}
91
Calculo punto inicial (start) y final (end) para las iteraciones de los ciclos basada en el número de hilos y número identificador del hilo
#define N 23
#define M 1000
#define numThreads 4
. . .
int start = ((N*M)/numThreads) * myID;
int end = ((N*M)/numThreads) * (myID+1);
. . .
if (myID == (numThreads-1)) end = N*M;
. . .
for (kj = start; kj < end; kj++) {
k = kj / M; j = kj % M;
w_new[k][j] = DoSomeWork(w[k][j], k, j);
}
(Gp:) Estas deben ser privadas para cada hilo
(Gp:) Asegúrate que todas las iteraciones se incluyen
Dividendo Iteraciones un Ciclo – Divide en Segmentos
92
#define N 23
#define M 5323
#define numThreads 16
. . .
int start = ((N*M)/numThreads) * myID;
int end = ((N*M)/numThreads) * (myID+1);
. . .
if (myID == (numThreads-1)) end = N*M;
. . .
for (kj = start; kj < end; kj++) { . . . }
23 * 5323 = 122,429 iteraciones
(Gp:) 13 iteracionesextras!
122,429 / 16 = 7651.8125
#define N 23
#define M 5323
#define numThreads 16
. . .
int start = (int)((float)(N*M)/numThreads) * myID;
int end = (int)((float)(N*M)/numThreads) * (myID+1);
. . .
if (myID == (numThreads-1)) end = N*M;
. . .
for (kj = start; kj < end; kj++) { . . . }
(float)
(float)
Dividendo Iteraciones del Ciclo – Balanceo de carga
93
Rango de valores de myID es [0..numThreads-1]
Buen balanceo de cargaen el número de iteraciones
Entre ±1 entre cualquiera de los hilos
Fácilmente codificado, no se pueden perder iteraciones
Ten cuidado de problemas potenciales de acceso a memoria y caché
#define N 23
#define M 1000
#define numThreads 4
. . .
for (kj = myID; kj < N*M; kj+=numThreads) {
k = kj / M;
j = kj % M;
w_new[k][j] = DoSomeWork(w[k][j], k, j);
}
(Gp:) Cada hilo hace cada iteración (numThreads)th
Dividendo Iteraciones del Ciclo – Turno Rotatorio
94
ACTIVIDAD: Paralelismo de Ciclos
¿Qué tipo de asignación se utilizaría en los siguientes cálculos para dividir las iteraciones entre los hilos?
Computar el siguiente cuadro de una película animada por computadora
Ciclo sobre renglones
Ciclo sobre pixeles en un renglón (columnas)
Calcula pixel
95
ACTIVIDAD: Paralelismo de Ciclos
Buscar a través del catálogo de una librería para encontrar cuántos libros tienen la palabra “loop” en el título
Un ciclo sobre las letras del alfabeto
Un ciclo sobre los autores con la primera letra en el nombre
Un ciclo sobre los libros por autor
Incrementar el contador global si el titulo tiene “loop
96
El Patrón Maestro/Esclavo
Problema
¿Como debe un programa estar organizado cuando el diseño es dominado por la necesidad de un balancear dinámicamente el trabajo en un conjunto de tareas?
Contexto
Balancear la cargas de las tarea también domina la porción serial y causa sobrecarga
Las cargas de trabajo de las tareas es variable e impredecible
Porciones de código computacionalmente intensivas no mapean a ciclos simples
Capacidad de núcleos en el sistema varían, cambian, impredecible
Particularmente relevante para el patrón de Paralelismo de Tareas
97
El Patrón Maestro/Esclavo
Forces
Trabajo impredecible por tarea requiere una lógica de asignación dinámica
Operaciones de balanceo de carga crean sobrecarga en la sincronización
Menos tareas y más largas pueden reducir esto, pero restringen opciones
Mantener el equilibrio entre balanceo de carga y mantener el código
98
El Patrón Maestro/Esclavo – Solución
Hilo Maestro
Inicia el cómputo
Controla la distribución de tareas a ser asignada a los hilos esclavos
Hilos Esclavos
Están en un ciclo mientras haya más tareas por hacerse
Aceptan tareas del hilo maestro
Ejecutan cada tarea asignada
Consideraciones en la Programación
Distribución de tareas
Detectar terminación y disposición de los esclavos
99
El Patrón Maestro/Esclavo Detectando Terminación
Rendezvous
Enviar una señal de terminación a cada esclavo
Hasta que se recibe una tarea, los esclavos checan si hay nuevo trabajo o la terminación de la tarea
100
El Patrón Maestro/Esclavo Detectando Terminación
Bolsa de tareas
Si todas las tareas están inicialmente cargadas en una bolsa, una bolsa vacía significa que el cómputo se completó
Añadir la terminación de tareas en la cola de tareas, después de todo el cálculo
Por simplicidad, añade una tarea de terminación por hilo esclavo
Shared Monotonic Counter
Counter greater than number of known tasks signals completion
101
CASO DE ESTUDIO: Implementación Rendezvous en el Código Maestro
LockSyncObject(BWlock);// sincroniza acceso al contador num_waiting
num_waiting++;
if (num_waiting !=2) { // si no hay esclavo esperando…
UnlockSyncObject(BWLock);
SleepUntilWorkerArrives(); // …espera
}
else {
WakeUpSleepingWorkerThread(); // despierta al esclavo
num_waiting = 0; // resetea para el siguiente rendezvous
UnlockSyncObject(BWLock);
}
< TRANSFIERE DATOS, ASIGNA UNA TAREA NUEVA O ENVÍA TERMINACIÓN>
102
CASO DE ESTUDIO: Implementación Rendezvous, Código del Hilo Esclavo
LockSyncObject(WorkerLock);//asegura la exclusion de otros esclavos
LockSyncObject(BWlock);//sincroniza acceso al contador num_waiting
num_waiting++;
if (num_waiting !=2) { // si el maestro no está esperando…
UnlockSyncObject(BWLock);
SleepUntilBossArrives(); // …espera
}
else {
WakeUpSleepingBossThread(); // despierta al maestro
num_waiting = 0; // resetea para el siguiente rendezvous
UnlockSyncObject(BWLock);
}
< TRANSFIERE DATOS, ASIGNA UNA TAREA NUEVA O ENVÍA TERMINACIÓN>
UnlockSyncObject(WorkerLock);//permite el siguiente esclavo a rendezvous
103
ACTIVITY: Boss/Worker
What type of task distribution method would be used on the following computations to divide iterations among threads?
Compute Mandlebrot set
Loop over rows
Loop over pixels in a row (columns)
Compute pixel
104
ACTIVIDAD: Maestro/Esclavo
Search through library catalog to find how many books have “loop” in the title
Loop over letters of alphabet
Loop over authors with first letter in name
Loop over books by author
Increment global counter if title has “loop”
105
Agenda
Patrón de estructura de lenguaje
El patrón de paralelismo de tareas
El patrón de descomposición geométrica
Estructuras de Soporte
Resumen
 Página anterior | Volver al principio del trabajo | Página siguiente  |